翻訳と辞書
Words near each other
・ Binary Goppa code
・ Binary Hammer
・ Binary hardening
・ Binary heap
・ Binary icosahedral group
・ Binary image
・ Binary Independence Model
・ Binary Integer Decimal
・ Binary lambda calculus
・ Binary Land
・ Binary large object
・ Binary liquid
・ Binary logarithm
・ Binary logic
・ Binary matroid
Binary moment diagram
・ Binary multiplier
・ Binary number
・ Binary object
・ Binary octahedral group
・ Binary offset carrier modulation
・ Binary operation
・ Binary opposition
・ Binary option
・ Binary Ordered Compression for Unicode
・ Binary pattern (image generation)
・ Binary Peaks
・ Binary plan
・ Binary prefix
・ Binary prioritization


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Binary moment diagram : ウィキペディア英語版
Binary moment diagram
A binary moment diagram (BMD) is a generalization of the binary decision diagram (BDD) to linear functions over domains such as booleans (like BDDs), but also to integers or to real numbers.
They can deal with boolean functions with complexity comparable to BDDs, but also some functions that are dealt with very inefficiently in a BDD are handled easily by BMD, most notably multiplication.
The most important properties of BMD is that, like with BDDs, each function has exactly one canonical representation, and many operations can be efficiently performed on these representations.
The main features that differentiate BMDs from BDDs are using linear instead of pointwise diagrams, and having weighted edges.
The rules that ensure the canonicity of the representation are:
* Decision over variables higher in the ordering may only point to decisions over variables lower in the ordering.
* No two nodes may be identical (in normalization such nodes all references to one of these nodes should be replaced be references to another)
* No node may have all decision parts equivalent to 0 (links to such nodes should be replaced by links to their always part)
* No edge may have weight zero (all such edges should be replaced by direct links to 0)
* Weights of the edges should be coprime. Without this rule or some equivalent of it, it would be possible for a function to have many representations, for example 2''x'' + 2 could be represented as 2 · (1 + ''x'') or 1 · (2 + 2''x'').
== Pointwise and linear decomposition ==

In pointwise decomposition, like in BDDs, on each branch point we store result of all branches separately. An example of such decomposition for an integer function (2''x'' + ''y'') is:
:\begin \text x
\begin
\text y , 3
\\
\text \neg y , 2
\end
\\
\text \neg x
\begin
\text y \text 1
\\
\text \neg y \text 0
\end
\end
In linear decomposition we provide instead a default value and a difference:
:\begin
\text
\begin
\text 0 \\
\text y , +1
\end
\\
\text x , +2
\end
It can easily be seen that the latter (linear) representation is much more efficient in case of additive functions, as when we add many elements the latter representation will have only O(''n'') elements, while the former (pointwise), even with sharing, exponentially many.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Binary moment diagram」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.